Reed-Solomon RS error correcting codes are applicable to a wide variety of environments. The most noteable examples are data storage, such as on optical disc media or solid state media, and long-distance data transmissions, such as from deep space to earth.
RS encoded data comprises codewords each having a predetermined number of symbols. When RS encoded data is stored or transmitted, the value of one or more symbols in a codeword may become corrupt, i.e. become changed to an incorrect value or become unknown. This is termed a symbol error. In some environments, the location of a corrupt symbol can be predicted and declared in advance of decoding (e.g. because data could not be read from a storage media, or part of a data transmission was not received). This is termed a symbol erasure. The term errata refers generally to either errors or erasures.
Most RS decoders handle only errors. However, some known RS decoders are able to perform decoding handling both errors and erasures. Here, the decoder receives erasure information, which indicates the location of zero or more suspected corrupt symbols within a codeword. Conveniently, a one bit erasure indicator is applied to each symbol, to indicate whether that symbol has been declared as an erasure. An RS (B,B-2T) code forms codewords of length B and is mathematically guaranteed to correct up to T symbol errors, and up to 2T symbols erasures, or any pattern of E symbol errors and J symbol erasures, provided that 2E+J≦2T. To correct an error, the decoder must find both its location and its magnitude, whereas to correct an erasure, only the magnitude of the correction must be found. Hence, erasure information allows more corrupt symbols to be corrected, compared with the situation where the erasure information is not available.
When a received codeword is passed to the decoder for decoding, the number of declared erasures is known. However, the number of errors is not known and must be determined by the decoder. On occasion, a codeword is encountered which is so severely corrupted that the decoder is unable to provide a reliable, mathematically accurate, correction, i.e. the received codeword is uncorrectable. It is important in many practical environments to determine that an uncorrectable codeword has been received.
An example prior art apparatus for detecting uncorrectable error patterns is disclosed in U.S. Pat. No. 5,099,482 (Idaho Research Foundation). However, this prior art apparatus is not applicable to a Reed-Solomon decoder that is able to handle both errors and erasures.
An aim of the present invention is to provide a method and apparatus for identifying uncorrectable Reed-Solomon codewords in the presence of errors and erasures. A preferred aim is to distinguish between correctable and uncorrectable codewords accurately and cost-efficiently.